package com.onpositive.simple.persistance;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Stack ;
import java.util.EmptyStackException ;

import com.sun.xml.internal.ws.api.pipe.NextAction;

abstract public class TreeSearchIndex<K> extends SearchIndex<K> {

	protected AbstractNodeStorage nodeStorage ;
	
	final protected int nodeMaxOrder, halfNodeOrder, nodeSize ;
	final protected int typeIndicatorBitsCount, zeroRecordOffset, parentNodeOffset, zeroSubtreeOffset ;
	protected int rootIndex ;
	
	protected final int emptySubtreeIndicator = -1 ;	
	protected final int recSize = 3, keyPos = 0, idPos = 1, subtrPos = 2  ;
	boolean firstRecord = true ;
	
	protected Stack<Integer> deletedNodes ;
	
	String type ;
	
	public TreeSearchIndex(Class<K> clazz, int m, AbstractNodeStorage storage ) {

// node structure is as follows
// Node = |info|R1|...|Rm||fatherNode|root|T0|...|Tm|
// where "info" stores type in the first bit and recordsCount in the rest,		
// Ri = |key|id| is a record,
// "fatherNode" is a pointer to fatherNode
// in a 0-type Node "root" is a pointer to subtree with same key sorted by id
		
		super(clazz);
		this.type = type ;
		deletedNodes = new Stack<Integer>() ;
		nodeMaxOrder = 2*m ;
		halfNodeOrder = m ;
		
		rootIndex = 0 ;
		typeIndicatorBitsCount = 1 ;
		zeroRecordOffset = 1 ;
		parentNodeOffset = zeroRecordOffset + recSize*nodeMaxOrder ;
		zeroSubtreeOffset =  parentNodeOffset + 1 ;
		
		nodeSize = zeroSubtreeOffset + nodeMaxOrder + 1 ;//		 
		
		nodeStorage = storage ;
		nodeStorage.masterIndex = this ;
	}
	static int getNodeSize( int m ){
		
		int _recSize = 3 ;
		int _nodeMaxOrder = 2*m ;
		
		int _zeroRecordOffset = 1 ;
		int _parentNodeOffset = _zeroRecordOffset + _recSize*_nodeMaxOrder ;
		int _zeroSubtreeOffset = _parentNodeOffset + 1 ;
		
		int _nodeSize = _zeroSubtreeOffset + _nodeMaxOrder + 1 ;
				
		return _nodeSize ; 
	}
	
	

	@Override
	protected void submitObject( int keyId, int objectId)
	{
		int record[] = constructRecord( keyId, objectId) ;
		if(firstRecord)
		{
			AbstractTreeNode treeNode = nodeStorage.getNewNode() ;
			treeNode.setElement(0, 2) ;
			for( int i = 0 ; i < recSize ; i++ )
				treeNode.setElement( zeroRecordOffset+i  , record[i] ) ;
			
			nodeStorage.putNode( treeNode,treeNode.getIndex() ) ;
			
			firstRecord = false ;			
		}
		else{
			AbstractTreeNode closestNode = findClosestNode(record, nodeStorage.getNode(rootIndex) ) ;
			appendRecord( record, closestNode ) ;
		}
	}

	@Override
	protected void removeObject( int keyId, int objectId)
	{		
		int record[] = constructRecord( keyId, objectId) ;
		 AbstractTreeNode closestNode = findClosestNode(record, nodeStorage.getNode(rootIndex) ) ;
		if( exactlyContains( record, closestNode ) ) ;	
			remove( record, closestNode.getIndex() ) ;
		
	}
	@Override
	int[] query( boolean requiresSubinterval,	boolean includeLowerBound,	boolean includeUpperBound,
			Object _lowerBound, Object _upperBound, Object _targetValue )
	{
		if( !requiresSubinterval )
			return findByKey( indexClass.cast(_targetValue) ) ;
		
		K lowerBound = indexClass.cast( _lowerBound ) ;
		K upperBound = indexClass.cast( _upperBound ) ;
		
		if( isLess_kk( upperBound, lowerBound )  )
			return null ;
		
		if( isEqual_kk( upperBound, lowerBound )  )
			return findByKey( lowerBound ) ;
		
		AbstractTreeNode lowerNode = findClosestNode( lowerBound, nodeStorage.getNode(rootIndex) ) ;
		AbstractTreeNode upperNode = findClosestNode( upperBound, nodeStorage.getNode(rootIndex) ) ;
		
		ArrayList<Integer> idArray = new ArrayList<Integer>() ;
		
		int lPos = findKeyPosition_u( lowerBound, lowerNode ) ;
		int uPos = findKeyPosition_l( upperBound, upperNode ) ;
		
		boolean gotLowerBound = lPos >= 0 ;
		boolean gotUpperBound = uPos >= 0 ;
		
		if( !gotLowerBound ) lPos = lPos*(-1)-1 ;
		if( !gotUpperBound ) uPos = uPos*(-1)-1 ;
		
		dumpId( idArray, lowerBound, lowerNode, lPos, !gotLowerBound || includeLowerBound,
						 upperBound, upperNode, uPos, !gotUpperBound || includeUpperBound  ) ;
		
		int result[] = new int[ idArray.size() ] ;
		for(int i = 0 ; i < result.length ; i++ )
			result[i] = idArray.get(i) ;
		
		return result ;
	}
	
	private void dumpId(ArrayList<Integer> idArray, K lowerBound, AbstractTreeNode lowerNode, int glPos, boolean passLowerIndex,
													K upperBound, AbstractTreeNode upperNode, int guPos, boolean passUpperindex  )
	{
		AbstractTreeNode seqPeak = getCommonAncestor( lowerNode, upperNode ) ;
		
		int accendingSequence[]  = produceAccendingSequence( lowerNode, seqPeak, glPos+1 );
		int descendingSequence[] = produceDescendingSequence( upperNode, seqPeak, guPos-1 );

		int wayUpLength = accendingSequence.length >> 1 ;
		int wayDownLength = descendingSequence.length >> 1 ;
		
		int peakStartRecord = -1;
		int peakEndRecord = -1 ;
		{
			int peakRecordsCount = seqPeak.getElement(0) >> typeIndicatorBitsCount ;
			if( wayUpLength == 0 )
				peakStartRecord = glPos ;
			else{
				int leftPeakSubtree = accendingSequence [ 2*( wayUpLength - 1 ) ] ;
				for( int i = 0 ; i < peakRecordsCount+1 ; i++ ){
					int subtreeIndex = seqPeak.getElement(zeroSubtreeOffset+i) ;
					if( subtreeIndex == leftPeakSubtree  ) peakStartRecord = i ;
				}
			}
			if( wayDownLength == 0 )
				peakEndRecord = guPos ;
			else{
				int rightPeakSubtree = wayDownLength == 0 ? guPos : descendingSequence[ 0 ] ;
				for( int i = 0 ; i < peakRecordsCount+1 ; i++ ){
					int subtreeIndex = seqPeak.getElement(zeroSubtreeOffset+i) ;
					if( subtreeIndex == rightPeakSubtree ) peakEndRecord   = i ;
				}
			}
		}		
		
		int subtreeIndex ;
		if( wayUpLength > 0 ){
			if ( passLowerIndex ){
					
				idArray.add( lowerNode.getElement(zeroRecordOffset + recSize*glPos + idPos ) ) ;
				int sameKeySubtreeRoot = lowerNode.getElement(zeroRecordOffset + recSize*glPos + subtrPos ) ;
				if( sameKeySubtreeRoot != emptySubtreeIndicator )
					dumpId(nodeStorage.getNode(sameKeySubtreeRoot), idArray) ;
			}
			if( true ){
				subtreeIndex = lowerNode.getElement(zeroSubtreeOffset+glPos+1) ;
				if( subtreeIndex != emptySubtreeIndicator )
					dumpId(nodeStorage.getNode( subtreeIndex ), idArray ) ;
			}
		}
		

		for( int i = 0 ; i < wayUpLength ; i ++ ){
			
			AbstractTreeNode treeNode = nodeStorage.getNode( accendingSequence[2*i] ) ;
			int recordsCount = treeNode.getElement(0) >> typeIndicatorBitsCount ;
			
			for( int j = accendingSequence[2*i+1] ; j < recordsCount ; j++ ){
				
				idArray.add( treeNode.getElement(zeroRecordOffset + recSize*j + idPos ) ) ;
				int sameKeySubtreeRoot = treeNode.getElement(zeroRecordOffset + recSize*j + subtrPos ) ;
				if( sameKeySubtreeRoot != emptySubtreeIndicator )
					dumpId(nodeStorage.getNode(sameKeySubtreeRoot), idArray) ;
				
				subtreeIndex = treeNode.getElement(zeroSubtreeOffset+j+1) ;
				if( subtreeIndex != emptySubtreeIndicator )				
					dumpId(nodeStorage.getNode( subtreeIndex ), idArray ) ;
			}				
		}
		
		idArray.add( seqPeak.getElement( zeroRecordOffset + recSize*peakStartRecord + idPos ) ) ;
		
		
		for( int i = peakStartRecord+1 ; i < peakEndRecord ; i++ )
		{
			subtreeIndex = seqPeak.getElement(zeroSubtreeOffset+i) ;
			if( subtreeIndex != emptySubtreeIndicator )
				dumpId(nodeStorage.getNode( subtreeIndex ), idArray ) ;
			
			idArray.add( seqPeak.getElement( zeroRecordOffset + recSize*i + idPos ) ) ;
			int sameKeySubtreeRoot = seqPeak.getElement( zeroRecordOffset + recSize*i + subtrPos ) ;
			if( sameKeySubtreeRoot != emptySubtreeIndicator )
				dumpId(nodeStorage.getNode(sameKeySubtreeRoot), idArray) ;			
		}
		
		
		for( int i = 0 ; i < wayDownLength ; i ++ ){
			
			AbstractTreeNode treeNode = nodeStorage.getNode( descendingSequence[2*i] ) ;
			
			for( int j = 0 ; j < descendingSequence[2*i+1] ; j++ ){
				
				subtreeIndex = treeNode.getElement(zeroSubtreeOffset+j ) ;
				if( subtreeIndex != emptySubtreeIndicator )
					dumpId(nodeStorage.getNode( subtreeIndex ), idArray ) ;
				
				idArray.add( treeNode.getElement(zeroRecordOffset + recSize*j + idPos ) ) ;
				int sameKeySubtreeRoot = treeNode.getElement(zeroRecordOffset + recSize*j + subtrPos ) ;
				if( sameKeySubtreeRoot != emptySubtreeIndicator )
					dumpId(nodeStorage.getNode(sameKeySubtreeRoot), idArray) ;				
			}				
		}
		
		if( wayDownLength > 0 ){
			subtreeIndex = upperNode.getElement( zeroSubtreeOffset+guPos ) ;
			if( subtreeIndex != emptySubtreeIndicator )		
				dumpId(nodeStorage.getNode( subtreeIndex ), idArray ) ;
			
			if ( passUpperindex ){
				
				idArray.add( upperNode.getElement(zeroRecordOffset + recSize*guPos + idPos ) ) ;
				int sameKeySubtreeRoot = upperNode.getElement(zeroRecordOffset + recSize*guPos + subtrPos ) ;
	
				if( sameKeySubtreeRoot != emptySubtreeIndicator )
					dumpId(nodeStorage.getNode(sameKeySubtreeRoot), idArray) ;
			}
		}				
	}

	private int[] produceAccendingSequence(AbstractTreeNode lowLevelNode, AbstractTreeNode highLevelNode, int lPos) {
		
		ArrayList<Integer> tmpArray  = new ArrayList<Integer>();
		
		AbstractTreeNode treeNode = nodeStorage.getNode( lowLevelNode.getIndex() ) ;
		for( ; treeNode.getIndex() != highLevelNode.getIndex() ;
			 treeNode = nodeStorage.getNode(treeNode.getElement(parentNodeOffset)) )
		{
			tmpArray.add(treeNode.getIndex()) ;			
		}
		
		int sequenceLength = tmpArray.size() ;
		int result[] = new int[ 2*sequenceLength ] ;
		if( sequenceLength == 0 )
			return result ;
		
		for( int i = 0 ; i < sequenceLength ; i++ )
			result[2*i] = tmpArray.get(i) ;
		
		result[1] = lPos ;
		//int recordsCount ;
		for( int i = 1 ; i < sequenceLength ; i++ ){
			
			treeNode = nodeStorage.getNode( result[2*i] ) ;
			//recordsCount = treeNode.getElement(0) >> typeIndicatorBitsCount ;
		
			int j = 0 ;
			for( ; treeNode.getElement( zeroSubtreeOffset+j )!= result[2*(i-1)] ; j++ ) ;
			result[2*i+1] = j ;				
		}
		return result;
	}
	
	private int[] produceDescendingSequence(AbstractTreeNode lowLevelNode, AbstractTreeNode highLevelNode, int uPos) {
		
		ArrayList<Integer> tmpArray  = new ArrayList<Integer>();
		
		AbstractTreeNode treeNode = nodeStorage.getNode( lowLevelNode.getIndex() ) ;
		for( ; treeNode.getIndex() != highLevelNode.getIndex() ;
			 treeNode = nodeStorage.getNode(treeNode.getElement(parentNodeOffset)) )
		{
			tmpArray.add(treeNode.getIndex()) ;			
		}
		
		int sequenceLength = tmpArray.size() ;
		int resultTmp[] = new int[ 2*sequenceLength ] ;
		if( sequenceLength == 0 )
			return resultTmp ;
		
		for( int i = 0 ; i < sequenceLength ; i++ )
			resultTmp[2*i] = tmpArray.get(i) ;
		
		resultTmp[1] = uPos+1 ;
		//int recordsCount ;
		for( int i = 0 ; i < sequenceLength-1 ; i++ ){
			
			treeNode = nodeStorage.getNode( resultTmp[2*(i+1)] ) ;
			//recordsCount = treeNode.getElement(0) >> typeIndicatorBitsCount ;
		
			int j = 0 ;
			for( ; treeNode.getElement( zeroSubtreeOffset+j )!= resultTmp[2*i] ; j++ ) ;
			resultTmp[2*(i+1)+1] = j ;
		}
		int result[] = new int[ 2*sequenceLength ] ;
		
		for( int i = 0 ; i < sequenceLength ; i++ ){
			result[2*i  ] = resultTmp[2*(sequenceLength-1-i)  ] ;
			result[2*i+1] = resultTmp[2*(sequenceLength-1-i)+1] ;
		}
		
		return result;
	}



	private AbstractTreeNode getCommonAncestor( AbstractTreeNode node1, AbstractTreeNode node2) {
		
		HashSet<Integer> set = new HashSet<Integer>() ;
		set.add(node1.getIndex()) ;
		int parentIndex = node1.getElement(parentNodeOffset) ;
		
		for( ; parentIndex != emptySubtreeIndicator ; )
		{
			set.add(parentIndex) ;
			node1 = nodeStorage.getNode(parentIndex) ;
			parentIndex = node1.getElement(parentNodeOffset) ;			
		}
		for( ; !set.contains(node2.getIndex()) ; )
		{
			parentIndex = node2.getElement(parentNodeOffset) ;
			node2 = nodeStorage.getNode(parentIndex) ;						
		}
		return node2;
	}



	private int findKeyPosition_u( K key, AbstractTreeNode treeNode ){
	// pos = min{ rec_index : rec_index >= key } ;	
		int recordsCount = treeNode.getElement(0) >> typeIndicatorBitsCount ;
		
		int pos = 0 ;
		for(  ; (pos < recordsCount) && isLess_k( treeNode.getElement( zeroRecordOffset + recSize*pos + keyPos), key ) ; pos++ ) ;
		
		if (pos == recordsCount)
			pos-- ;// = pos*(-1)-1 ;
		else
			if( !isEqual_k(key, treeNode.getElement(zeroRecordOffset + recSize*pos + keyPos) ) )
				pos = pos*(-1)-1 ;
		
		return pos ;
	}
	
	private int findKeyPosition_l( K key, AbstractTreeNode treeNode ){
		// pos = max{ rec_index : rec_index <= key } ;	
			int recordsCount = treeNode.getElement(0) >> typeIndicatorBitsCount ;
			
			int pos = recordsCount-1 ;
			for(  ; (pos > 0 ) && isGreater_k( treeNode.getElement( zeroRecordOffset + recSize*pos + keyPos), key ) ; pos-- ) ;
			
			if (pos == -1 )
				pos++ ; // = pos*(-1)-1 ;
			else
				if( !isEqual_k(key, treeNode.getElement(zeroRecordOffset + recSize*pos + keyPos) ) )
					pos = pos*(-1)-1 ;
			
			return pos ;
		}

	public int[] findByKey( K key ){
		
		AbstractTreeNode closestNode = findClosestNode( key, nodeStorage.getNode(rootIndex) ) ;
		int record[] = getRecordByKey( closestNode, key ) ;
		
		if ( record == null ){
			int[] emptyResult = {-1} ;
			return emptyResult ;
		}
		
		int id = record[ idPos ] ;
		int sameKeySubtreeRoot = record[ subtrPos ];
		
		ArrayList<Integer> idArray = new ArrayList<Integer>() ;
		idArray.add( record[ idPos ] ) ;
		
		if( ( id != emptySubtreeIndicator ) && ( sameKeySubtreeRoot != emptySubtreeIndicator ) )
			dumpId( nodeStorage.getNode(sameKeySubtreeRoot), idArray ) ;

		int idArraySize = idArray.size() ;
		int result[] = new int[idArraySize] ;
		for( int i = 0 ; i < idArraySize ; i++ )
			result[i] = idArray.get(i) ;
		
		return result ;		
	}	
	
	private int[] getRecordByKey( AbstractTreeNode treeNode, K key ){
		
		int pos = findKeyPosition_u(key, treeNode) ;
		
		if( pos >= 0 ){
			int record[] = new int[recSize] ;
			for( int j = 0 ; j < recSize ; j++ )
				record[j] = treeNode.getElement( zeroRecordOffset+ recSize*pos + j ) ;
				
				return record ;
			}
		else
			return null ;		
	}
	protected int[] constructRecord(int keyId, int objectId) {
		int record[] = new int[this.recSize] ;
		record[   keyPos ] = keyId ; //stringStorage.put( (String)key ) ;
		record[    idPos ] = objectId ;
		record[ subtrPos ] = emptySubtreeIndicator ;
		
		return record;
	}

	private void dumpId( AbstractTreeNode treeNode, ArrayList<Integer> idArray )
	{
		int recordsCount = getRecordsCount(treeNode), subtreeIndex ;
		
		for( int i = 0 ; i < recordsCount ; i++ )
		{
			subtreeIndex = treeNode.getElement(zeroSubtreeOffset+i) ;
			if( subtreeIndex != emptySubtreeIndicator )
				dumpId(nodeStorage.getNode( subtreeIndex ), idArray );
			
			idArray.add( treeNode.getElement(zeroRecordOffset+recSize*i + idPos) ) ;

			int nodeType = treeNode.getElement(0) & ( (1<<typeIndicatorBitsCount)-1 ) ;
			if( nodeType == 1 ){
				int sameKeySubtreeRoot = treeNode.getElement(zeroRecordOffset + recSize*i + subtrPos );
				if( sameKeySubtreeRoot != emptySubtreeIndicator )
					dumpId(nodeStorage.getNode(sameKeySubtreeRoot), idArray) ;
		
				}
		}	

		subtreeIndex = treeNode.getElement( zeroSubtreeOffset+recordsCount  ) ;
		if( subtreeIndex != emptySubtreeIndicator )
			dumpId(nodeStorage.getNode( subtreeIndex ), idArray );			
	}	
		
	private void insertRecord( int[] record, AbstractTreeNode treeNode, int leftSubtree, int rightSubtree, int parentalOffset )
	{
		int nodeRecordsCount = treeNode.getElement(0) >> typeIndicatorBitsCount  ;
		int newNodeRecords[] = new int[recSize*(nodeRecordsCount+1)] ;
		int newNodeSubtrees[] = new int[nodeRecordsCount+2] ;
		
		constructTemporaryNode( treeNode, newNodeRecords , newNodeSubtrees , leftSubtree, rightSubtree,  record ) ;
		
		if( newNodeRecords.length > nodeMaxOrder*recSize )
		{
			AbstractTreeNode newNode = nodeStorage.getNewNode() ; 
			int newRecord[] = new int[recSize] ;
			
			splitBetweenNodes( newNodeRecords, newNodeSubtrees, treeNode, newNode, newRecord ) ;
			
			nodeStorage.putNode(treeNode, treeNode.getIndex()) ;
			nodeStorage.putNode(newNode, newNode.getIndex()) ;

			int parentIndex = treeNode.getElement( parentNodeOffset ) ;
			AbstractTreeNode parentNode ;
			
			
			if( ( parentIndex != emptySubtreeIndicator ) ){
				
				parentNode = nodeStorage.getNode( parentIndex ) ;
				int parentType = parentNode.getElement(0) & 1 ;
				int nodeType = treeNode.getElement(0) & 1 ;
				
				if( parentType != nodeType ){
					
					AbstractTreeNode parentSubtreeNode = nodeStorage.getNewNode() ;
					parentSubtreeNode.setElement( parentNodeOffset, parentIndex ) ;
					//parentSubtreeNode.setElement( 0, 3 ) ;
					parentNode.setElement( zeroRecordOffset + recSize*parentalOffset + subtrPos , parentSubtreeNode.getIndex() ) ;
					
					insertRecord( newRecord, parentSubtreeNode, treeNode.getIndex(), newNode.getIndex(), parentalOffset ) ;
				}
				else
					insertRecord( newRecord, parentNode, treeNode.getIndex(), newNode.getIndex(),  parentalOffset ) ;
			}
				
			else{
				parentNode = nodeStorage.getNewNode() ;
				rootIndex = parentNode.getIndex() ;
					insertRecord( newRecord, parentNode, treeNode.getIndex(), newNode.getIndex(), parentalOffset ) ;
			}
			
		}
		else{
			
			for( int i = 0 ; i < newNodeRecords.length ; i++ )
				treeNode.setElement( zeroRecordOffset + i , newNodeRecords[i] );
			
			for( int i = 0 ; i < newNodeSubtrees.length ; i++ )
				treeNode.setElement( zeroSubtreeOffset + i , newNodeSubtrees[i] );
			
			int nodeType = getType(treeNode) ; 
			treeNode.setElement( 0 , ( nodeRecordsCount+1 << typeIndicatorBitsCount ) + nodeType ) ;
			
			nodeStorage.putNode( treeNode, treeNode.getIndex()) ;
		}										
	}
	private void constructTemporaryNode( AbstractTreeNode treeNode, int newNodeRecords[], int newNodeSubtrees[], int leftSubtree,
										 int rightSubtree, int record[] )
	{
		int nodeRecordsCount = getRecordsCount( treeNode ) ;
		int nodeType = getType( treeNode ) ;
		int subtreeIndex = 0 ;
		
		if( nodeType == 0 ){
			for( ; ( subtreeIndex < nodeRecordsCount ) &&
					isLess( treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + nodeType ), record[nodeType] ) ;	subtreeIndex++ )
			{
				for( int j = 0 ; j < recSize ; j++ )
					newNodeRecords[ recSize*subtreeIndex + j ] = treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + j ) ;
				
				newNodeSubtrees[subtreeIndex] = treeNode.getElement( zeroSubtreeOffset + subtreeIndex ) ;
			}		
		}
		else{
			for( ; ( subtreeIndex < nodeRecordsCount ) && 
					treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + nodeType ) < record[nodeType] ; subtreeIndex++ )
			{
				for( int j = 0 ; j < recSize ; j++ )
					newNodeRecords[ recSize*subtreeIndex + j ] = treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + j ) ;
				
				newNodeSubtrees[subtreeIndex] = treeNode.getElement( zeroSubtreeOffset + subtreeIndex ) ;
			}
		
		}
		try{
			for( int j = 0 ; j < recSize ; j++ )
				newNodeRecords[ recSize*subtreeIndex + j ] = record[j] ;
		}
		catch( ArrayIndexOutOfBoundsException e){
			@SuppressWarnings("unused")
			int k = 9 ;
		}

		newNodeSubtrees[subtreeIndex  ] = leftSubtree ;
		newNodeSubtrees[subtreeIndex+1] = rightSubtree ;
	
		if( leftSubtree != emptySubtreeIndicator )
			setParent( leftSubtree, treeNode.getIndex() ) ;
		
		if( rightSubtree != emptySubtreeIndicator )
			setParent( rightSubtree, treeNode.getIndex() ) ;

		for( int i = subtreeIndex ; i < nodeRecordsCount ; i++ )
		{
			for( int j = 0 ; j < recSize ; j++ )
				newNodeRecords[ recSize*(i+1)+j ] = treeNode.getElement( zeroRecordOffset + recSize*i+j ) ;
			
			newNodeSubtrees[ i + 2] = treeNode.getElement( zeroSubtreeOffset+i+1 ) ;
		}
	}

	private void splitBetweenNodes( int[] newNodeRecords, int[] newNodeSubtrees, AbstractTreeNode treeNode, AbstractTreeNode newNode, int[] newRecord )
	{	
		for( int i = 0 ; i < halfNodeOrder*recSize ; i++ ){
			treeNode.setElement( zeroRecordOffset + i , newNodeRecords[i]); //left half of the new records goes to the old node
			newNode.setElement( zeroRecordOffset + i , newNodeRecords[ recSize*( halfNodeOrder+1 ) + i ]);//the right half goes to the new one
		}
		
		for( int j = 0 ; j < recSize ; j++ )
			newRecord[j] = newNodeRecords[ recSize*halfNodeOrder + j ] ; // center records are extracted into the separate array
				
		for( int i = 0 ; i < halfNodeOrder+1 ; i++ ){
			treeNode.setElement( zeroSubtreeOffset + i , newNodeSubtrees[i]);//left half of the new subtrees goes to the old node
			int childIndex = newNodeSubtrees[ halfNodeOrder+1+i] ;
			newNode.setElement( zeroSubtreeOffset + i , childIndex);//the right half goes to the new one
			
			if( childIndex != emptySubtreeIndicator )
				setParent( childIndex, newNode.getIndex() ) ;
		}
		int nodeType = treeNode.getElement(0) & ( (1<<typeIndicatorBitsCount) -1 ) ;
		int zeroFieldValue = ( halfNodeOrder << typeIndicatorBitsCount ) + nodeType ;
		treeNode.setElement(0, zeroFieldValue) ;
		newNode.setElement(0, zeroFieldValue) ;
	}
	
	private  AbstractTreeNode findClosestNode( int[] record,  AbstractTreeNode treeNode )
	{
		SubtreeChoiceEqualFlag equal = new SubtreeChoiceEqualFlag(false) ;
		int subtreeIndex = chooseSubtree( treeNode, record, equal  ) ;
		
		if( equal.equal )
		{
			if( getType(treeNode ) == 1 ){ //last possible field in the record
				return treeNode ;
			}
			else{
				int sameKeySubtreeRoot = -1; //getNextSameKeyIndex( treeNode ) ;

				if( sameKeySubtreeRoot == emptySubtreeIndicator )
					return treeNode ;
				else
					return  findClosestNode( record, nodeStorage.getNode( sameKeySubtreeRoot ) ) ;
			}
		}
		else{
			int subtreeRootIndex = treeNode.getElement( zeroSubtreeOffset + subtreeIndex ) ; 
		
			if( subtreeRootIndex == emptySubtreeIndicator )
				return treeNode ;
			else
				return findClosestNode( record,  nodeStorage.getNode( subtreeRootIndex ) ) ;
		}			
	}
	
	private void appendRecord( int[] record,  AbstractTreeNode treeNode )
	{
		SubtreeChoiceEqualFlag equal = new SubtreeChoiceEqualFlag(false) ;
		int subtreeIndex = chooseSubtree( treeNode, record, equal  ) ;
	
		if( equal.equal )
		{
			if( getType(treeNode) == 1 ){ //last possible field in the record
				//do nothing because the record (key,id) already exists
			}
			else{
				//we are right in a 0-type node, which has an empty sameKey tree
				int sameKeySubtreeRoot = treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + subtrPos ) ;
				if( sameKeySubtreeRoot == emptySubtreeIndicator )
					appendSameKeySubtree( subtreeIndex, record, treeNode  ) ;
				else{
					AbstractTreeNode sameKeyNodeRoot = nodeStorage.getNode(sameKeySubtreeRoot) ;
					insertRecord( record, sameKeyNodeRoot, emptySubtreeIndicator, emptySubtreeIndicator, subtreeIndex ) ;
				}					
			}
		}
		else
			insertRecord( record, treeNode, emptySubtreeIndicator, emptySubtreeIndicator, -1 ) ;
	}	
		
	private void appendSameKeySubtree( int subtreeIndex, int[] record, AbstractTreeNode parentNode )
	{
		AbstractTreeNode treeNode = nodeStorage.getNewNode() ;
		
		treeNode.setElement( 0, 3 );
		for( int i = 0 ; i < recSize ; i++ )
			treeNode.setElement( zeroRecordOffset + i, record[i] );
		
		parentNode.setElement( zeroRecordOffset + recSize*subtreeIndex + subtrPos ,treeNode.getIndex() );
		treeNode.setElement( parentNodeOffset, parentNode.getIndex() ) ;
		
		nodeStorage.putNode( treeNode , treeNode.getIndex() ) ;
		nodeStorage.putNode( parentNode , parentNode.getIndex() ) ;
	}
	
	private boolean exactlyContains( int[] record, AbstractTreeNode treeNode )
	{
		int nodeRecordsCount = treeNode.getElement(0) >> typeIndicatorBitsCount ;
		
		for( int i = 0 ; i < nodeRecordsCount ; i++ ){
			int recordOffset = zeroRecordOffset + i*recSize ;
			if( ( treeNode.getElement( recordOffset ) == record[0] ) && ( treeNode.getElement( recordOffset+1 ) == record[1] ) )
				return true ;
		}			
		return false ;
	}
	
	private void remove( int[] record,  int nodeIndex )
	{
		
	}
	
	int getRecordsCount( AbstractTreeNode treeNode )
	{
		return treeNode.getElement(0) >> typeIndicatorBitsCount ;
	}
	
	int getType(  AbstractTreeNode treeNode )
	{
		return treeNode.getElement(0) & (( 1<<typeIndicatorBitsCount )-1) ;
	}
	
	void setParent( int nodeIndex , int parentIndex  )
	{
		
		AbstractTreeNode treeNode = nodeStorage.getNode(nodeIndex) ;
		treeNode.setElement(parentNodeOffset, parentIndex) ;
		nodeStorage.putNode(treeNode, nodeIndex) ;
	}
	
	int chooseSubtree( AbstractTreeNode treeNode, int record[], SubtreeChoiceEqualFlag equalFlag  )
	{
		int nodeType = getType( treeNode ) ;
		int nodeRecordsCount = getRecordsCount(treeNode) ;
		
		int subtreeIndex = 0 ;
		if( nodeType == 0 ){
			if( isGreater( record[nodeType], treeNode.getElement( zeroRecordOffset + recSize*(nodeRecordsCount-1) + nodeType ) ) )
			{
				subtreeIndex = nodeRecordsCount ;
				equalFlag.equal = false ;
			}
			else{	
				for( ; ( subtreeIndex < nodeRecordsCount-1 ) && 
						isLess( treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + nodeType ), record[nodeType] ) ;	subtreeIndex++ ) ;
				
				equalFlag.equal = isEqual( treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + nodeType ), record[nodeType] ) ;
			}
		}
		else{
			if( record[nodeType] > treeNode.getElement( zeroRecordOffset + recSize*(nodeRecordsCount-1) + nodeType ) )
			{
				subtreeIndex = nodeRecordsCount ;
				equalFlag.equal = false ;
			}
			else{
				for( ; ( subtreeIndex < nodeRecordsCount-1 ) && 
						(treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + nodeType ) < record[nodeType] ) ; subtreeIndex++ ) ;
		
				equalFlag.equal = ( treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + nodeType ) == record[nodeType] ) ;
			}
		}
		return subtreeIndex ;
	}
	
	abstract protected boolean isLess( int arg1, int arg2 );// return  arg1 < arg2 ;
	abstract protected boolean isLessEqual( int arg1, int arg2 );// return  arg1 <= arg2 ;
	abstract protected boolean isGreater( int arg1, int arg2 );// return  arg1 < arg2 ;
	abstract protected boolean isGreaterEqual( int arg1, int arg2 );// return  arg1 <= arg2 ;
	abstract protected boolean isEqual( int arg1, int arg2 );// return arg1 == arg2 ;
	
	abstract protected boolean isLess_k( K key, int arg );
	abstract protected boolean isLessEqual_k( K key, int arg );
	abstract protected boolean isLess_k( int arg, K key );
	abstract protected boolean isLessEqual_k( int arg, K key );
	abstract protected boolean isGreater_k( K key, int arg );
	abstract protected boolean isGreaterEqual_k( K key, int arg );
	abstract protected boolean isGreater_k( int arg, K key );
	abstract protected boolean isGreaterEqual_k( int arg, K key );
	
	abstract protected boolean isEqual_k( K key, int arg );
	
	abstract protected boolean isLess_kk( K key1, K key2 );
	abstract protected boolean isEqual_kk( K key1, K key2 );
	
	private AbstractTreeNode findClosestNode( K key, AbstractTreeNode treeNode )
	{
		SubtreeChoiceEqualFlag equal = new SubtreeChoiceEqualFlag(false) ;
		int subtreeIndex = chooseSubtree( treeNode, key, equal  ) ;
		
		if( equal.equal )
		{
			return treeNode ;
		}
		else{
			int subtreeRootIndex = treeNode.getElement( zeroSubtreeOffset + subtreeIndex ) ; 
		
			if( subtreeRootIndex == emptySubtreeIndicator )
				return treeNode ;
			else
				return findClosestNode( key, nodeStorage.getNode( subtreeRootIndex ) ) ;
		}			
	}
	
	int chooseSubtree(  AbstractTreeNode treeNode, K key, SubtreeChoiceEqualFlag equalFlag  )
	{
		int nodeType = getType( treeNode ) ;
		int nodeRecordsCount = getRecordsCount(treeNode) ;
		
		int subtreeIndex = 0 ;
		if( isGreater_k( key, treeNode.getElement( zeroRecordOffset + recSize*(nodeRecordsCount-1) + nodeType ) ) )
		{
			subtreeIndex = nodeRecordsCount ;
			equalFlag.equal = false ;
		}
		else{	
			for( ; ( subtreeIndex < nodeRecordsCount-1 ) && 
					isLess_k( treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + nodeType ), key ) ;	subtreeIndex++ ) ;
			
			equalFlag.equal = isEqual_k( key, treeNode.getElement( zeroRecordOffset + recSize*subtreeIndex + nodeType ) ) ;
		}
		
		return subtreeIndex ;
	}

}
